FIG. 1 illustrates a conventional tree structure, as is well known in the prior art, for searching a data structure to match a table entry with a search key associated with a message packet to determine processing steps required to send the message packet to its destination. This example is specifically for a “Longest Prefix Match” lookup as is required for a routing table. The search is started by using the first “X” number of bits (in this case, 16 bits) of a search key of “n” number of bits to index into the direct table 10. Then a Patricia tree structure 12 (bits 16-23) is used to resolve collisions for multiple routes that share the same entry in the direct table by the use of Pattern Search Control Blocks 14. Each Pattern Search Control Block 14 (PSCB) is configured to test one of the remaining untested bits in the search key (IP address). Each PSCB decodes one bit to a “0” or a “1”. Note that each PSCB in the path to the route represents a memory access required to complete the search. Thus, one obvious limitation of this approach is the latency of the search which is dominated by these memory accesses. Memory bandwidth also becomes an issue. Eventually, this process will lead to a unique route required for routing packets with the current IP address to their destination. These routes are denoted in the figure with a circle enclosing an “R”. Additional circles enclosing a “P” indicate routes that are prefixes of other routes. In these cases, the search must continue past the prefix in order to determine if a longer prefix route exists, but may return to the prefix if no better match is found for the current address.
In this application, different terms, including abbreviations and acronyms, are used. Table I listed below gives a definition of certain of the terms:
TABLE ITerms (including abbreviations and acronyms)TermDefinitionNPANext PSCB addressNBTNext bit to testLCBALeaf control block addressBirdPrefix of a prefix or nested prefixTrail End FlagEnd of search - entry points to a leafSRAMStatic random access memoryDRAMDynamic random access memoryDTDirect tableD . . .DRAM identifierMemMemoryLPMLongest prefix matchPSCBPattern Search Control Block